package LeetCode.题库.困难;

import org.junit.Test;

/**
 * @author 挚爱之夕
 * @date 2022-03-08 - 03 - 08 - 12:49
 * @Description 给定两个大小分别为 m 和 n 的正序（从小到大）数组nums1 和nums2
 * 请你找出并返回这两个正序数组的 中位数
 * 算法的时间复杂度应该为 O(log (m+n))
 * @Version 困难
 */
public class _4寻找两个正序数组的中位数 {
    static int[] nums1 = {1, 2};
    static int[] nums2 = {3, 4};
    @Test
    public void solve(){
        double res = findMedianSortedArrays(nums1, nums2);
        System.out.println(res);
    }
    /*by me 辅助数组*/
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int m = nums1.length, n = nums2.length;
        int[] nums3 = new int[m + n];
        int p1 = 0, p2 = 0, cur = 0;
        int n1, n2;
        //得到合并的数组
        while(p1 < nums1.length || p2 < nums2.length){
            if(p1 >= nums1.length){//第一个数组遍历完了
                nums3[cur++] = nums2[p2++];
                continue;
            }
            if(p2 >= nums2.length){//第二个数组遍历完了
                nums3[cur++] = nums1[p1++];
                continue;
            }
            //两个数组都还有值
            n1 = nums1[p1];
            n2 = nums2[p2];
            //取较小的
            if(n1 < n2){
                nums3[cur++] = nums1[p1++];
            }else{
                nums3[cur++] = nums2[p2++];
            }
        }
        //合并数组的长度
        int len = m + n;
        //考虑只有一个元素的情况
        if(len == 1){
            return nums3[0];
        }
        //考虑元素个数奇偶的情况
        if(len % 2 == 0){
            return (nums3[len / 2 - 1]  + nums3[len / 2]) / 2.0;
        }else{
            return nums3[len / 2];
        }
    }
    /*官方思路*/

}
